Least Frequently Used (LFU) is a type of
cache algorithm
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to m ...
used to manage
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remember ...
within a computer. The standard characteristics of this method involve the system keeping track of the number of times a
block
Block or blocked may refer to:
Arts, entertainment and media Broadcasting
* Block programming, the result of a programming strategy in broadcasting
* W242BX, a radio station licensed to Greenville, South Carolina, United States known as ''96.3 ...
is
referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.
LFU is sometimes combined with a
Least Recently Used
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to ...
algorithm and called LRFU.
Implementation
The simplest method to employ an LFU algorithm is to assign a counter to every block that is loaded into the cache. Each time a reference is made to that block the counter is increased by one. When the cache reaches capacity and has a new block waiting to be inserted the system will search for the block with the lowest counter and remove it from the cache.
* Ideal LFU: there is a counter for each item in the catalogue
* Practical LFU: there is a counter for the items stored in cache. The counter is forgotten if the item is evicted.
Problems
While the LFU method may seem like an intuitive approach to memory management it is not without faults. Consider an item in memory which is referenced repeatedly for a short period of time and is not accessed again for an extended period of time. Due to how rapidly it was just accessed its counter has increased drastically even though it will not be used again for a decent amount of time. This leaves other blocks which may actually be used more frequently susceptible to purging simply because they were accessed through a different method.
Moreover, new items that just entered the cache are subject to being removed very soon again, because they start with a low counter, even though they might be used very frequently after that. Due to major issues like these, an explicit LFU system is fairly uncommon; instead, there are hybrids that utilize LFU concepts.
[B.T. Zivkoz and A.J. Smith]
Disk Caching in Large Database and Timeshared Systems
IEEE MASCOTS, 1997
See also
*
Paging
In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage ...
*
Page Replacement Algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page repl ...
*
Not Frequently Used
References
External links
An O(1) algorithm for implementing the LFU cache eviction scheme 16 August 2010, by Ketan Shah, Anirban Mitra and Dhruv Matani
{{DEFAULTSORT:Least frequently used
Virtual memory
Memory management algorithms
Online algorithms